6122. Простой стек
Реализуйте
структуру данных “стек”. Напишите
программу, содержащую описание стека и моделирующую работу стека, реализовав
все указанные методы. Программа считывает последовательность команд и в
зависимости от команды выполняет ту или иную операцию. После выполнения каждой
команды программа должна вывести одну строку. Возможные команды для программы:
·
push n
– Добавьте в стек число n (значение n
задается после команды). Выведите ok.
·
pop – Удалите из стека последний элемент. Выведите его значение.
·
back – Выведите значение последнего
элемента, не удаляя его из стека.
·
size – Выведите количество элементов в
стеке.
·
clear – Очистите стек и выведите ok.
·
exit – Выведите bye и завершите
работу.
Гарантируется,
что набор входных команд удовлетворяет следующим требованиям: максимальное
количество элементов в стеке в любой момент не превосходит 100, все команды pop
и back корректны, то есть при их исполнении в стеке содержится хотя бы
один элемент.
Вход. Каждая строка
содержит одну команду.
Выход. Для каждой команды
выведите в отдельной строке соответствующий результат.
|
Пример
входа |
Пример
выхода |
|
push 2 push 3 push 5 back size pop size push 7 pop clear size exit |
ok ok ok 5 3 5 2 ok 7 ok 0 bye |
РЕШЕНИЕ
стек
Анализ алгоритма
В задаче следует
промоделировать работу стека.
Реализация алгоритма
#include <cstdio>
#include <cstring>
#include <stack>
using namespace
std;
stack<int> s;
char str[100];
int n;
int main(void)
{
while(scanf("%s",str))
{
if
(strcmp(str,"push") == 0)
{
scanf("%d",&n);
s.push(n);
puts("ok");
} else
if
(strcmp(str,"pop") == 0)
{
printf("%d\n",s.top());
s.pop();
} else
if
(strcmp(str,"back") == 0)
{
printf("%d\n",s.top());
} else
if (strcmp(str,"size")
== 0)
{
printf("%d\n",s.size());
} else
if
(strcmp(str,"clear") == 0)
{
while(!s.empty())
s.pop();
puts("ok");
} else
{
puts("bye");
break;
}
}
return 0;
}
Реализация алгоритма –
STL cin, cout
Объявим рабочий стек.
stack<int> s;
Читаем команду str. Команды читаем до конца файла.
while(cin >> str)
{
if (str == "push")
{
Команда push. Читаем число n и заносим его в стек. Выводим сообщение “ok”.
cin >> n;
s.push(n);
cout
<< "ok" << endl;
} else
if (str == "pop")
{
Команда pop. Выводим число на вершине стека. Удаляем верхний элемент.
cout << s.top() << endl;
s.pop();
} else
if (str == "back")
{
Команда top. Выводим число на вершине стека.
cout << s.top() << endl;
} else
if (str == "size")
{
Команда size. Выводим размер стека.
cout << s.size() << endl;
} else
if (str == "clear")
{
Команда clear. Удаляем весь стек. Поскольку С++ не имеет для стека метода
clear, то приходится последовательно
удалять элементы стека один за другим.
while(!s.empty())
s.pop();
cout << "ok"
<< endl;
} else
{
Команда exit. Выводим “bye” и завершаем работу программы.
cout << "bye"
<< endl;
break;
}
}
return 0;
}
Реализация алгоритма –
собственный класс
Объявим класс Стек и его методы.
class Stack {
public:
Stack(int
_size);
~Stack();
void push(int v);
int pop();
int back();
int size();
void clear();
void exit();
private:
int* m;
int _size;
};
Stack::Stack(int _size = 110) {
m = new int[_size];
this->_size
= 0;
}
Stack::~Stack()
{
delete[] m;
}
void Stack::push(int
v) {
m[_size++] = v;
puts("ok");
}
int Stack::pop() {
return
m[--_size];
}
int Stack::back() {
return
m[_size-1];
}
int Stack::size() {
return _size;
}
void Stack::clear() {
_size = 0;
puts("ok");
}
void Stack::exit() {
puts("bye");
}
Основная часть
программы. Моделируем работу стека.
Stack s;
while(scanf("%s",&str))
{
if
(strcmp(str,"push") == 0)
{
scanf("%d",&n);
s.push(n);
} else
if
(strcmp(str,"pop") == 0)
{
printf("%d\n",s.pop());
} else
if
(strcmp(str,"back") == 0)
{
printf("%d\n",s.back());
} else
if
(strcmp(str,"size") == 0)
{
printf("%d\n",s.size());
} else
if
(strcmp(str,"clear") == 0)
{
s.clear();
} else
{
s.exit();
break;
}
}
Java реализация – статический массив
import java.util.*;
//import java.io.*;
class Stack
{
private int m[];
private int size;
public Stack(int size)
{
m = new int[size];
this.size = 0;
}
public void push(int v)
{
m[size++] = v;
System.out.println("ok");
}
public int pop()
{
return m[--size];
}
public int back()
{
return m[size-1];
}
public int size()
{
return size;
}
public void clear()
{
size = 0;
System.out.println("ok");
}
public void exit()
{
System.out.println("bye");
}
}
public class Main
{
public static void main(String[] args) //throws IOException
{
Stack s = new Stack(110);
//Scanner con = new Scanner(new FileReader
("6122.in"));
Scanner
con = new Scanner(System.in);
while(true)
{
String str = con.next();
if (str.equals("push"))
{
int n = con.nextInt();
s.push(n);
} else
if (str.equals("pop"))
{
System.out.println(s.pop());
} else
if (str.equals("back"))
{
System.out.println(s.back());
} else
if (str.equals("size"))
{
System.out.println(s.size());
} else
if (str.equals("clear"))
{
s.clear();
} else
{
s.exit();
break;
}
}
con.close();
}
}
Java реализация – встроенный стек
import java.util.*;
//import java.io.*;
public class Main
{
public static void main(String[] args) //throws IOException
{
Stack<Integer> s = new Stack<Integer>();
//Scanner con = new Scanner(new FileReader
("6122.in"));
Scanner con = new Scanner(System.in);
while(true)
{
String str = con.next();
if (str.equals("push"))
{
int n = con.nextInt();
s.push(n);
System.out.println("ok");
} else
if (str.equals("pop"))
{
System.out.println(s.pop());
} else
if (str.equals("back"))
{
System.out.println(s.peek());
} else
if (str.equals("size"))
{
System.out.println(s.size());
} else
if (str.equals("clear"))
{
s.clear();
System.out.println("ok");
} else
{
System.out.println("bye");
break;
}
}
con.close();
}
}
Java реализация – LinkedList
import java.util.*;
//import java.io.*;
class Stack
{
private
LinkedList<Integer> m;
public Stack()
{
m = new LinkedList<Integer>();
}
public void push(int v)
{
m.add(v);
System.out.println("ok");
}
public int pop()
{
int val = m.getLast();
m.removeLast();
return val;
}
public int back()
{
return m.getLast();
}
public int size()
{
return m.size();
}
public void clear()
{
m.clear();
System.out.println("ok");
}
public void exit()
{
System.out.println("bye");
}
}
public class Main
{
public static void main(String[] args) //throws IOException
{
Stack s = new Stack();
//Scanner con = new Scanner(new FileReader
("6122.in"));
Scanner
con = new Scanner(System.in);
while(true)
{
String str = con.next();
if (str.equals("push"))
{
int n = con.nextInt();
s.push(n);
} else
if (str.equals("pop"))
{
System.out.println(s.pop());
} else
if (str.equals("back"))
{
System.out.println(s.back());
} else
if (str.equals("size"))
{
System.out.println(s.size());
} else
if (str.equals("clear"))
{
s.clear();
} else
{
s.exit();
break;
}
}
con.close();
}
}
Java реализация – расширенный стек
import java.util.*;
class MyStack
{
protected Vector<Integer> v;
MyStack()
{
v = new
Vector<Integer>();
}
public void push(int x)
{
v.add(x);
}
public int pop()
{
int last = v.lastElement();
v.remove(v.size() - 1);
return last;
}
}
class NewStack extends MyStack
{
public void push(int x)
{
super.push(x);
System.out.println("ok");
}
/*
public int pop() // pop is totally the same as in superclass
{
return super.pop();
}
*/
public int back()
{
return v.get(v.size() - 1);
// v is visible from subclass, it is protected
}
public int size()
{
return v.size();
}
public void clear()
{
v.clear();
System.out.println("ok");
}
public void exit()
{
System.out.println("bye");
}
}
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
NewStack s = new NewStack();
while(true)
{
String str = con.next();
if (str.equals("push"))
{
int n = con.nextInt();
s.push(n);
} else
if (str.equals("pop"))
{
System.out.println(s.pop());
} else
if (str.equals("back"))
{
System.out.println(s.back());
} else
if (str.equals("size"))
{
System.out.println(s.size());
} else
if (str.equals("clear"))
{
s.clear();
} else
{
s.exit();
break;
}
}
con.close();
}
}
Python реализация
import sys
stack = []
for str in
sys.stdin:
lst = list(str.split())
if
lst[0] == "push":
n = int(lst[1]);
stack.append(n);
print("ok")
elif
lst[0] == "pop":
print(stack.pop())
elif
lst[0] == "back":
print(stack[-1])
elif
lst[0] == "size":
print(len(stack))
elif
lst[0] == "clear":
stack.clear()
print("ok")
else:
print("bye")
break;